lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/grafos/prim.cpp

   1 #include <stdio.h>
   2 #include <string>
   3 #include <set>
   4 #include <vector>
   5 #include <queue>
   6 #include <iostream>
   7 #include <map>
   8
   9 using namespace std;
  10
  11 typedef string node;
  12 typedef pair<double, node> edge;
  13 typedef map<node, vector<edge> > graph;
  14
  15
  16 int main(){
  17   double length;
  18   while (cin >> length){
  19     int cities;
  20     cin >> cities;
  21     graph g;
  22     for (int i=0; i<cities; ++i){
  23       string s;
  24       cin >> s;
  25       g[s] = vector<edge>();
  26     }
  27     int edges;
  28     cin >> edges;
  29     for (int i=0; i<edges; ++i){
  30       string u, v;
  31       double w;
  32       cin >> u >> v >> w;
  33       g[u].push_back(edge(w, v));
  34       g[v].push_back(edge(w, u));
  35     }
  36
  37     double total = 0.0;
  38     priority_queue<edge, vector<edge>, greater<edge> > q;
  39     q.push(edge(0.0, g.begin()->first));
  40     set<node> visited;
  41     while (q.size()){
  42       node u = q.top().second;
  43       double w = q.top().first;
  44       q.pop(); //!!
  45
  46       if (visited.count(u)) continue;
  47
  48       visited.insert(u);
  49       total += w;
  50       vector<edge> &vecinos = g[u];
  51       for (int i=0; i<vecinos.size(); ++i){
  52         node v = vecinos[i].second;
  53         double w_extra = vecinos[i].first;
  54         if (visited.count(v) == 0){
  55           q.push(edge(w_extra, v));
  56         }
  57       }
  58     }
  59
  60     if (total > length){
  61       cout << "Not enough cable" << endl;
  62     }else{
  63       printf("Need %.1lf miles of cable\n", total);
  64     }
  65
  66   }
  67   return 0;
  68 }